package com.hanxiaozhang.no10leetcode.backtrack;

import java.util.ArrayList;
import java.util.List;

/**
 * 〈一句话功能简述〉<br>
 * 〈〉
 * 给一个不重复的整数集合，返回所有可能的子集合
 * 实例:
 * 输入: nums = [1,2,3]
 * 输出: [[], [3], [2], [2, 3], [1], [1, 3], [1, 2] , [1, 2, 3]]
 * <p>
 * 整体思路（灵魂）：
 * -- 每次递归处理 保存当前值 和 不保存当前值 两种情况，递归到结束条件时，保存结果。
 * -- 每次递归后，需要恢复现场。
 * <p>
 * 具体步骤：
 * 构建一个递归方法：
 * -- 递归入参：需要技巧
 * --- results  结果
 * --- curResult  本次结果
 * --- nums   数组
 * --- index 处理位置
 * -- 逻辑：
 * --- 边界条件：index == nums.length 时，加入结果，注意 new ArrayList()
 * --- 结果中不保存当前值时，backTract(... index + 1)
 * ---- 结果中保存当前值时， i. 添加元素 ；ii. 调用 backTrack(... index + 1)； iii. 删除元素，恢复现场
 *
 * @author hanxinghua
 * @create 2024/2/19
 * @since 1.0.0
 */
public class No78Subsets {

    public static void main(String[] args) {

        int[] nums = {1, 2, 3};

        System.out.println(method1(nums));

    }


    private static List<List<Integer>> method1(int[] nums) {

        List<List<Integer>> results = new ArrayList<>();
        if (nums == null || nums.length < 1) {
            return results;
        }
        List<Integer> curResult = new ArrayList<>();
        backTract(results, curResult, nums, 0);
        return results;
    }

    /**
     * 递归
     *
     * @param results   结果
     * @param curResult 本次结果
     * @param nums      数组
     * @param index     处理位置
     */
    private static void backTract(List<List<Integer>> results, List<Integer> curResult, int[] nums, int index) {

        // 边界条件
        if (index == nums.length) {
            results.add(new ArrayList<>(curResult));
            return;
        }
        // 结果中不保存当前值
        backTract(results, curResult, nums, index + 1);
        // 结果中保存当前值
        curResult.add(nums[index]);
        backTract(results, curResult, nums, index + 1);
        // 恢复现场
        curResult.remove(curResult.size() - 1);
    }


}
